package complexity;

import java.util.Iterator;

public class TwoWayLinkList<T> implements Iterable<T>{
    private Node head ;
    private Node last ;
    private int N;
    private class Node{
        private Node pre;
        private Node next;
        private T data;
        public Node(Node pre, Node next, T data) {
            this.pre = pre;
            this.next = next;
            this.data = data;
        }
    }
    public TwoWayLinkList(){
        //初始化头节点和尾节点 初始化长度
        this.head= new Node(null,null,null);
        this.last= head;
        this.last.next=head;
        this.N=0;
    }
    public void clear(){
        this.N=0;
        this.last=null;
        this.head.next=null;
        this.head.pre=null;
    }
    public int length(){
        return this.N;
    }
    public boolean isEmpty(){
        return this.N==0;
    }
    public T getFirstEle() throws Exception {
        if (isEmpty()){
            throw  new Exception();
        }
        return head.next.data;
    }
    public T getLastEle(){
        if (isEmpty()){
            return null;
        }
        return last.data;
    }
    public void insert(T t){
        if (isEmpty()){
            Node node = new Node(head, null, t);
            this.last=node;
            head.next=last;
        }else {
            Node node = new Node(last, null, t);
            this.last.next=node;
            this.last=node;
        }
        this.N++;
    }
    public void insert(int index,T t) throws Exception {
        Node pre = head;
        for (int i = 0; i < index; i++) {
            pre=pre.next;
        }
        Node curr = pre.next;
        Node newNode = new Node(pre, curr, t);
        pre.next=newNode;
        curr.pre = newNode;
        this.N++;
//        if (isEmpty()){
//            insert(t);
//            return;
//        }
//        Node newNode = null;
//        if (index>this.N&&index==0){
//            throw new Exception("indexOutOfBoundsArray");
//        }
//        for (int i = 0; i < index; i++) {
//            newNode = this.head.next;
//        }
//        Node pre =  newNode.pre;
//        Node next = newNode.next;
//        Node node = new Node(pre, next, t);
//        pre.next=node;
//        next.pre=node;
//        this.N++;
    }
    public T get(int index) throws Exception {
        if (index>this.N){
            throw new Exception();
        }
        Node node =head.next;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node.data;
    }
    public int indexOf(T t){
        Node node = this.head;
        int count =0;
        while (node.next!=null){
            node = node.next;
            if (node.data.equals(t)){
                return  count;
            }
            count++;
        }
        return -1;
    }
    public T remove(int index){
        Node node = head.next;
        for (int i = 0; i < index; i++) {
            node=node.next;
        }
        Node pre = node.pre;
        Node next = node.next;
        pre.next=next;
        next.pre=pre;
        this.N--;
        return node.data;
    }
    @Override
    public Iterator<T> iterator() {
        return new TIterator();
    }
    class TIterator implements Iterator{
        private Node node;

        public TIterator() {
            this.node = head;
        }

        @Override
        public boolean hasNext() {
            return node.next!=null;
        }

        @Override
        public T next() {
            node= node.next;
            return node.data;
        }
    }
    public void reverse(){
        if (isEmpty()){
           return;
        }else {
            reverse(head.next);
        }
    }
    public Node reverse(Node node){
        if (node.next==null){
            head.next=node;
            return node;
        }
        Node pre = reverse(node.next);
        pre.next=node;
        node.next=null;
        return node;
    }
    public T getMidNode(){
        Node fast = head;
        Node slow = head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow.data;
    }
}
